package Solutions

import (
	"strconv"
	"strings"
)

type uf_17 struct {
	parent map[string]string
}

func (u *uf_17) find(s string) string {
	st := u.parent[s]
	if st == "" {
		u.parent[s] = s
		return s
	}
	if st != s {
		ss := u.find(st)
		u.parent[s] = ss
		return ss
	}
	return st
}

func (u *uf_17) union(s1, s2 string) {
	ps1, ps2 := u.find(s1), u.find(s2)
	if ps1 == ps2 {
		return
	} else if ps1 < ps2 {
		u.parent[ps2] = ps1
	} else {
		u.parent[ps1] = ps2
	}

}

func trulyMostPopular(names []string, synonyms []string) []string {
	uf := uf_17{}
	uf.parent = make(map[string]string)
	for _, v := range synonyms {
		childStrs := strings.Split(v, ",")
		uf.union(childStrs[0][1:], childStrs[1][:len(childStrs[1])-1])
	}
	var ansMp = make(map[string]int)
	for _, v := range names {
		childStrs := strings.Split(v, "(")
		count, _ := strconv.Atoi(childStrs[1][:len(childStrs[1])-1])
		p := uf.find(childStrs[0])
		ansMp[p] += count
	}
	ans := make([]string, 0, len(ansMp))
	for name, count := range ansMp {
		ans = append(ans, name+"("+strconv.Itoa(count)+")")
	}
	return ans

}
